{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[source](../../api/alibi_detect.cd.cvm_online.rst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Online Cramér-von Mises\n",
    "\n",
    "## Overview\n",
    "\n",
    "The online [Cramér-von Mises](https://en.wikipedia.org/wiki/Cram%C3%A9r%E2%80%93von_Mises_criterion) detector is a non-parametric method for online drift detection on continuous data. Like the [offline Cramér-von Mises](cvmdrift.ipynb) detector, it applies a univariate Cramér-von Mises (CVM) test to each feature. This detector is an adaptation of that proposed in [this paper](https://www.tandfonline.com/doi/abs/10.1080/00224065.2012.11917887) by Ross et al. <cite data-cite=\"Ross2012a\"><!-- --></cite>.\n",
    "\n",
    "<div class=\"alert alert-warning\">\n",
    "\n",
    "**Warning**\n",
    "    \n",
    "This detector is multi-threaded, with Numba used to parallelise over the simulated streams. There is a [known issue](https://github.com/SeldonIO/alibi-detect/issues/648) on MacOS, where Numba's default OpenMP [threading layer](https://numba.readthedocs.io/en/stable/user/threading-layer.html?highlight=thread_id#the-threading-layers) causes segfaults. A workaround is to use the slightly less performant `workqueue` threading layer on MacOS by setting the `NUMBA_THREADING_LAYER` enviroment variable or running:\n",
    "    \n",
    "```python\n",
    "from numba import config\n",
    "config.THREADING_LAYER = 'workqueue'\n",
    "```\n",
    "</div>\n",
    "\n",
    "### Threshold configuration\n",
    "Online detectors assume the reference data is large and fixed and operate on single data points at a time (rather than batches). These data points are passed into the test-windows, and a two-sample test-statistic between the reference data and test-window is computed at each time-step. When the test-statistic exceeds a preconfigured threshold, drift is detected. Configuration of the thresholds requires specification of the expected run-time (ERT) which specifies how many time-steps that the detector, on average, should run for in the absence of drift before making a false detection. Thresholds are then configured to target this ERT by simulating `n_bootstraps` number of streams of length `t_max = 2*max(window_sizes) - 1`. Conveniently, the non-parametric nature of the detector means that thresholds depend only on $M$, the length of the reference data set. Therefore, for multivariate data, configuration is only as costly as the univariate case.\n",
    "\n",
    "\n",
    "<div class=\"alert alert-info\">\n",
    "\n",
    "**Note**\n",
    "    \n",
    "In order to reduce the memory requirements of the threshold configuration process, streams are simulated in batches of size $N_{batch}$, set with the `batch_size` keyword argument. However, the memory requirements still scale with $O(M^2N_{batch})$. If configuration is requiring too much memory (or time), then consider subsampling the reference data. The quadratic growth of the cost with respect to the number of reference instances $M$, combined with the diminishing increase in test power, often makes this a worthwhile tradeoff.\n",
    "</div>\n",
    "\n",
    "### Window sizes\n",
    "Specification of test-window sizes (the detector accepts multiple windows of different size $W$) is also required, with smaller windows allowing faster response to severe drift and larger windows allowing more power to detect slight drift. Since this detector requires the windows to be full to function, the ERT is measured from `t = min(window_sizes)-1`.\n",
    "\n",
    "### Multivariate data\n",
    "Although this detector is primarly intended for univariate data, it can also be applied to multivariate data. In this case, the detector makes a correction similar to the Bonferroni correction used for the offline detector. Given $d$ features, the detector configures thresholds by targeting the $1-\\beta$ quantile of test statistics over the simulated streams, where $\\beta = 1 - (1-(1/ERT))^{(1/d)}$. For the univariate case, this simplifies to $\\beta = 1/ERT$. At prediction time, drift is flagged if the test statistic of any feature stream exceed the thresholds.\n",
    "\n",
    "<div class=\"alert alert-info\">\n",
    "\n",
    "**Note**\n",
    "    \n",
    "In the multivariate case, for the ERT's upper bound to be accurate, the feature streams must be independent. Regardless of independence, the ERT will still be properly lower bounded. \n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Usage\n",
    "\n",
    "### Initialize\n",
    "\n",
    "\n",
    "Arguments:\n",
    "\n",
    "* `x_ref`: Data used as reference distribution.\n",
    "* `ert`: The expected run-time in the absence of drift, starting from *t=min(windows_sizes)*.\n",
    "* `window_sizes`: The sizes of the sliding test-windows used to compute the test-statistics. Smaller windows focus on responding quickly to severe drift, larger windows focus on ability to detect slight drift.\n",
    "\n",
    "\n",
    "Keyword arguments:\n",
    "\n",
    "* `preprocess_fn`: Function to preprocess the data before computing the data drift metrics.\n",
    "* `n_bootstraps`: The number of bootstrap simulations used to configure the thresholds. The larger this is the more accurately the desired ERT will be targeted. Should ideally be at least an order of magnitude larger than the ERT.\n",
    "* `batch_size`: The maximum number of bootstrap simulations to compute in each batch when configuring thresholds. A smaller batch size reduces memory requirements, but can result in a longer configuration run time.\n",
    "* `n_features`: Number of features used in the FET test. No need to pass it if no preprocessing takes place. In case of a preprocessing step, this can also be inferred automatically but could be more expensive to compute.\n",
    "* `verbose`: Whether or not to print progress during configuration.\n",
    "* `input_shape`: Shape of input data.\n",
    "* `data_type`: Optionally specify the data type (tabular, image or time-series). Added to metadata.\n",
    "\n",
    "\n",
    "Initialized drift detector example:\n",
    "\n",
    "```python\n",
    "from alibi_detect.cd import CVMDriftOnline\n",
    "\n",
    "ert = 150\n",
    "window_sizes = [20,40]\n",
    "cd = CVMDriftOnline(x_ref, ert, window_sizes)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Detect Drift\n",
    "\n",
    "We detect data drift by sequentially calling `predict` on single instances `x_t` (no batch dimension) as they each arrive. We can return the test-statistic and the threshold by setting `return_test_stat` to *True*.\n",
    "\n",
    "The prediction takes the form of a dictionary with `meta` and `data` keys. `meta` contains the detector's metadata while `data` is also a dictionary which contains the actual predictions stored in the following keys:\n",
    "\n",
    "* `is_drift`: 1 if any of the test-windows have drifted from the reference data and 0 otherwise.\n",
    "\n",
    "* `time`: The number of observations that have been so far passed to the detector as test instances.\n",
    "\n",
    "* `ert`: The expected run-time the detector was configured to run at in the absence of drift.\n",
    "\n",
    "* `test_stat`: CVM test-statistics between the reference data and the test_windows if `return_test_stat` equals *True*.\n",
    "\n",
    "* `threshold`: The values the test-statsitics are required to exceed for drift to be detected if `return_test_stat` equals *True*.\n",
    "\n",
    "\n",
    "```python\n",
    "preds = cd.predict(x_t, return_test_stat=True)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Managing State\n",
    "\n",
    "The detector's state may be saved with the `save_state` method:\n",
    "\n",
    "```python\n",
    "cd = CVMDriftOnline(x_ref, ert, window_sizes)  # Instantiate detector at t=0\n",
    "cd.predict(x_1)  # t=1\n",
    "cd.save_state('checkpoint_t1')  # Save state at t=1\n",
    "cd.predict(x_2)  # t=2\n",
    "```\n",
    "\n",
    "The previously saved state may then be loaded via the `load_state` method:\n",
    "\n",
    "```python\n",
    "# Load state at t=1\n",
    "cd.load_state('checkpoint_t1')\n",
    "```\n",
    "\n",
    "At any point, the state may be reset to `t=0` with the `reset_state` method. When saving the detector with `save_detector`, the state will be saved, unless `t=0` (see [here](../../overview/saving.md#online-detectors))."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
